home *** CD-ROM | disk | FTP | other *** search
/ SuperHack / SuperHack CD.bin / CODING / C / CDLLIST.ZIP / LIST.C next >
Encoding:
C/C++ Source or Header  |  1993-06-01  |  14.0 KB  |  297 lines
  1. #define data_type    int
  2. #define name_of_list list_of_ints
  3.  
  4. #include "list.h"
  5. #include <stdio.h>
  6.  
  7. /***************************************************************************
  8. *  Procedure name : get_node                                               *
  9. *         Purpose : allocate storage for new nodes                         *
  10. *          Inputs : -                                                      *
  11. * Outputs/Returns : pointer to the new node                                *
  12. *       Called by : insert_before_cur, insert_after_cur                    *
  13. *           Calls : malloc, sizeof, printf                                 *
  14. *         Globals :                                                        *
  15. *                                                                          *
  16. ***************************************************************************/
  17. struct node *get_node()
  18. {
  19.     char *malloc(); struct node *p;
  20.  
  21.     p=(struct node *)malloc(sizeof(struct node));   /*allocate space*/
  22.     if (p==NULL) {printf("Not enough memory"); exit(1);}
  23.     return(p);             /*return new node*/
  24. }
  25.  
  26. /***************************************************************************
  27. *  Procedure name : goto_head                                              *
  28. *         Purpose : move current pointer to head of list                   *
  29. *          Inputs : list to use                                            *
  30. * Outputs/Returns : new current_pos pointer                                *
  31. *       Called by : initialize_list                                        *
  32. *           Calls : -                                                      *
  33. *         Globals :                                                        *
  34. *                                                                          *
  35. ***************************************************************************/
  36. void goto_head(name_of_list *a)
  37. {
  38.     a->current_pos=a->head;       /*set current pointer to head */
  39. }
  40.  
  41. /***************************************************************************
  42. *  Procedure name : goto_tail                                              *
  43. *         Purpose : move current pointer to tail of list                   *
  44. *          Inputs : list to be used                                        *
  45. * Outputs/Returns : new current_pos pointer                                *
  46. *       Called by : -                                                      *
  47. *           Calls : -                                                      *
  48. *         Globals :                                                        *
  49. *                                                                          *
  50. ***************************************************************************/
  51. void goto_tail(name_of_list *a)
  52. {
  53.     a->current_pos=a->tail;      /*set current pointer to tail*/
  54. }
  55.  
  56. /***************************************************************************
  57. *  Procedure name : goto_left                                              *
  58. *         Purpose : move current_position one node to the left             *
  59. *          Inputs : list to be traversed                                   *
  60. * Outputs/Returns : new current_pos pointer                                *
  61. *       Called by : -                                                      *
  62. *           Calls : -                                                      *
  63. *         Globals :                                                        *
  64. *                                                                          *
  65. ***************************************************************************/
  66. void goto_left(name_of_list *a)
  67. {
  68.     if (a->current_pos!=NULL)    /*if there is a node move to its left*/
  69.         a->current_pos=a->current_pos->left;
  70. }
  71.  
  72. /***************************************************************************
  73. *  Procedure name : goto_right                                             *
  74. *         Purpose : move current_position one node to the right            *
  75. *          Inputs : list to be traversed                                   *
  76. * Outputs/Returns : new current_pos pointer                                *
  77. *       Called by : position                                               *
  78. *           Calls : -                                                      *
  79. *         Globals :                                                        *
  80. *                                                                          *
  81. ***************************************************************************/
  82. void goto_right(name_of_list *a)
  83. {
  84.     if (a->current_pos!=NULL)   /*if there is a node move to its right*/
  85.         a->current_pos=a->current_pos->right;
  86. }
  87.  
  88. /***************************************************************************
  89. *  Procedure name : retrieve_current                                       *
  90. *         Purpose : retrieve value held in node pointed to by current_pos  *
  91. *          Inputs : list to retrieve value from                            *
  92. * Outputs/Returns : value held in data of current_pos node                 *
  93. *       Called by : -                                                      *
  94. *           Calls : -                                                      *
  95. *         Globals :                                                        *
  96. *                                                                          *
  97. ***************************************************************************/
  98. data_type retrieve_current(name_of_list *a)
  99. {
  100.     if (a->current_pos!=NULL)     /*if there is a node */
  101.         return(a->current_pos->data);      /* return its data*/
  102. }
  103.  
  104. /***************************************************************************
  105. *  Procedure name : size                                                   *
  106. *         Purpose : count how many nodes are in the list *a                *
  107. *          Inputs : list to be counted                                     *
  108. * Outputs/Returns : size of list in integer                                *
  109. *       Called by : delete_at_current                                      *
  110. *           Calls : -                                                      *
  111. *         Globals :                                                        *
  112. *                                                                          *
  113. ***************************************************************************/
  114. int size(name_of_list *a)
  115. {
  116.     struct node *temp=a->head;       /*start counting from the head*/
  117.     int count=1;
  118.  
  119.     while ((temp!=NULL)&&(temp->right!=a->head))
  120.         {                    /*increment counter until tail is*/
  121.         count++;             /*reached*/
  122.         temp=temp->right;
  123.         }
  124.     if (a->head==NULL) count=0;   /*if list is empty return 0*/
  125.  
  126.     return(count);
  127. }
  128.  
  129. /***************************************************************************
  130. *  Procedure name : insert_before_cur                                      *
  131. *         Purpose : insert a new node, with data b, before current_pos     *
  132. *          Inputs : list in which to insert *a, data element b             *
  133. * Outputs/Returns : new list with new node inserted                        *
  134. *       Called by : -                                                      *
  135. *           Calls : get_node                                               *
  136. *         Globals :                                                        *
  137. *                                                                          *
  138. ***************************************************************************/
  139. void insert_before_cur(name_of_list *a,data_type b)
  140. {
  141.     struct node *new;
  142.  
  143.     new=get_node();       /*get new node and place data into it*/
  144.     new->data=b;
  145.     if (a->head==NULL)        /*if list is empty*/
  146.         {
  147.         a->head=a->tail=a->current_pos=new;
  148.         new->right=new;
  149.         new->left=new;         /*make new only node in list*/
  150.         }
  151.     else
  152.         {
  153.         new->left=a->current_pos->left;
  154.         new->right=a->current_pos;   /*insert new node to left of*/
  155.         new->left->right=new;        /*current_pos*/
  156.         new->right->left=new;
  157.         if (a->current_pos==a->head)
  158.             a->head=a->current_pos->left;
  159.         }
  160. }
  161.  
  162. /***************************************************************************
  163. *  Procedure name : insert_after_cur                                       *
  164. *         Purpose : insert a new node, with data b, after current_pos      *
  165. *          Inputs : list to insert into *a, data element b                 *
  166. * Outputs/Returns : list with new node inserted into it                    *
  167. *       Called by : -                                                      *
  168. *           Calls : get_node                                               *
  169. *         Globals :                                                        *
  170. *                                                                          *
  171. ***************************************************************************/
  172. void insert_after_cur(name_of_list *a,data_type b)
  173. {
  174.     struct node *new;
  175.  
  176.     new=get_node();        /*get new node and place data into it*/
  177.     new->data=b;
  178.     if (a->head==NULL)        /*if list is empty*/
  179.         {
  180.         a->head=a->tail=a->current_pos=new;
  181.         new->right=new;
  182.         new->left=new;       /*make new node only node in list*/
  183.         }
  184.     else
  185.         {
  186.         new->left=a->current_pos;
  187.         new->right=a->current_pos->right;
  188.         new->left->right=new;      /*place new node to right of*/
  189.         new->right->left=new;      /*current_pos*/
  190.         if (a->current_pos==a->tail)
  191.             a->tail=a->current_pos->right;
  192.         }
  193. }
  194.  
  195. /***************************************************************************
  196. *  Procedure name : position                                               *
  197. *         Purpose : find the next occurence of b, beginning search at      *
  198. *                   current_pos                                            *
  199. *          Inputs : list to search through *a, key element b               *
  200. * Outputs/Returns : offset number of nodes from current that contains key  *
  201. *       Called by : -                                                       *
  202. *           Calls : -                                                       *
  203. *         Globals :                                                        *
  204. *                                                                          *
  205. ***************************************************************************/
  206. int position(name_of_list *a,data_type b)
  207. {
  208.     int count=0;
  209.     struct node *temp;
  210.  
  211.     temp=a->current_pos;     /*start searching at current_pos*/
  212.     while ((temp->data!=b)&&(temp!=a->tail)&&(temp!=NULL))
  213.         {                      /*traverse list until end is reached*/
  214.         temp=temp->right;      /*or key is found*/
  215.         count++;
  216.         }
  217.     if (temp->data!=b)      /*if the key wasn't found*/
  218.         count=-1;             /*set count to unique value*/
  219.     return(count);
  220. }
  221.  
  222. /***************************************************************************
  223. *  Procedure name : delete_at_current                                      *
  224. *         Purpose : delete and free node pointed to by current_pos         *
  225. *          Inputs : list to delete from                                    *
  226. * Outputs/Returns : new list sans one node                                 *
  227. *       Called by : initialize_list                                        *
  228. *           Calls : printf, free                                           *
  229. *         Globals :                                                        *
  230. *                                                                          *
  231. ***************************************************************************/
  232. void delete_at_current(name_of_list *a)
  233. {
  234.     struct node *temp;
  235.  
  236.     if (size(a)==1)          /*if list contains 1 element*/
  237.         {
  238.         free(a->current_pos);            /*remove the element*/
  239.         a->head=a->tail=a->current_pos=NULL;
  240.         }
  241.     else if (size(a)>1)          /*if list contains more than 1 element*/
  242.         {
  243.         if (a->current_pos==a->head)      /*check if head is to be*/
  244.             {                         /*deleted*/
  245.             a->head=a->head->right;
  246.             a->head->left=a->tail;     /*delete head and update*/
  247.             a->tail->right=a->head;    /*head pointer*/
  248.             free(a->current_pos);
  249.             a->current_pos=a->head;
  250.             }
  251.         else if (a->current_pos==a->tail) /*check if tail is to be*/
  252.             {                         /*deleted*/
  253.             a->tail=a->tail->left;
  254.             a->tail->right=a->head;  /*delete tail and update*/
  255.             a->head->left=a->tail;   /*tail pointer*/
  256.             free(a->current_pos);
  257.             a->current_pos=a->tail;
  258.             }
  259.         else       /*otherwise node to be deleted is in the middle*/
  260.             {
  261.             temp=a->current_pos->right;   /*delete it &*/
  262.             a->current_pos->left->right=a->current_pos->right;
  263.             a->current_pos->right->left=a->current_pos->left;
  264.             free(a->current_pos);         /*update pointers*/
  265.             a->current_pos=temp;
  266.             }
  267.         }
  268.     else
  269.         printf("List has no nodes to delete! No deletion done.");
  270. }                            /*return error message if no nodes exist*/
  271.  
  272. /***************************************************************************
  273. *  Procedure name : initialize_list                                        *
  274. *         Purpose : prepare list for use                                   *
  275. *          Inputs : list to be prepared                                    *
  276. * Outputs/Returns : empty list with pointers in tact                       *
  277. *       Called by : -                                                      *
  278. *           Calls : goto_head, delete_at_current                           *
  279. *         Globals :                                                        *
  280. *                                                                          *
  281. ***************************************************************************/
  282. void initialize_list(name_of_list *a)
  283. {
  284.     if ( ((a->head->left)==(a->tail)) && ((a->tail->right)==(a->head)) )
  285.         {              /*if list pointers are complete then*/
  286.         do{
  287.             goto_head(a);      /*delete all the nodes contained*/
  288.             delete_at_current(a);}
  289.         while(a->head!=NULL);
  290.         }
  291.     else                /*if list pointers aren't complete then*/
  292.         {
  293.         a->head=a->tail=a->current_pos=NULL;
  294.         }                     /* make them all NULL*/
  295. }
  296.  
  297.